一、SDNE [2016]

《Structural Deep Network Embedding》

1. 如今，网络无处不在，并且许多现实世界的 application 需要挖掘这些网络中的信息。例如，Twitter 中的推荐系统旨在从社交网络中挖掘用户偏好的推文，在线广告 targeting 通常需要将社交网络中的用户聚类到某些社区。因此，挖掘网络中的信息非常重要。这里的一个基本问题是：如何学习有用的 network representation？

   一种有效的方法是将网络嵌入到低维空间中，即学习每个顶点的 vector representation ，目的是在学到的 embedding 空间中重建网络。因此，网络中的信息挖掘，如信息检索（information retrieval ）、分类（classification）、聚类（clustering） ，都可以直接在低维空间中进行。

   学习 network representation 面临以下巨大挑战：

   • 高度非线性：网络的底层结构是高度非线性的，因此如何设计一个模型来捕获高度非线性的结构是相当困难的。

   • 结构保持（structure-preserving）：为了支持分析网络的 application，需要 network embedding 能够保持网络结构。然而，网络的底层结构非常复杂。顶点的相似性取决于局部网络结构 （local network structure ）和全局网络结构（global network structure ）。因此，如何同时保持局部结构和全局结构是一个棘手的问题。

   • 稀疏性：许多现实世界的网络通常非常稀疏，以至于仅利用非常有限观察到的链接不足以达到令人满意的性能。

   在过去的几十年中，人们已经提出了许多浅层模型的 network embedding 方法，如 IsoMap、Laplacian Eigenmaps: LE、LINE 。然而，由于浅层模型的表达能力有限，它们很难捕获到高度非线性的网络结构。尽管一些方法采用了核技巧（kernel technique），但是核方法也是浅层模型，也无法很好地捕获高度非线性的结构。为了很好地捕获高度非线性的结构，在论文《Structural Deep Network Embedding》 中，作者提出了一种新的深度模型来学习网络的vertex representation 。这是由深度学习最近的成功所推动的。深度学习已经被证明具有强大的表达能力来学习数据的复杂结构，并在处理图像数据、文本数据、音频数据方面取得了巨大成功。具体而言，在论文提出的模型中，作者设计了一个由多个非线性函数组成的多层架构。多层非线性函数的组合可以将数据映射到高度非线性的潜在空间中，从而能够捕获到高度非线性的网络结构。

   为了解决深度模型中的结构保持、以及稀疏性问题，作者进一步提出在学习过程中联合利用一阶邻近性（ first-order proximity ）和二阶邻近性（ second-order proximity ）。一阶邻近性是仅在由edge 连接的顶点之间的局部 pairwise 相似性，它刻画了局部网络结构。然而，由于网络的稀疏性，许多合法的链接（即未观测到的链接）发生缺失，结果导致一阶邻近性不足以表达网络结构。因此，作者进一步提出二阶邻近性来表示顶点邻域结构的相似性，从而捕获全局网络结构。通过一阶邻近性和二阶邻近性，我们可以分别很好地刻画局部网络结构和全局网络结构。

   顶点邻域也是一种局部网络结构，并不是全局网络结构。只是顶点邻域的 “ 局部” 要比顶点 pairwise 的范围更大。

   为了在深度模型中同时保留局部网络结构和全局网络结构，论文提出了一种半监督架构，其中无监督组件（unsupervised component）重建二阶邻近性从而保留全局网络结构，而监督组件（ supervised component ）利用一阶邻近性作为监督信息从而保留局部网络结构。因此，学到的 representation 可以很好地保留局部网络结构和全局网络结构。此外，如下图所示，具有二阶邻近性的 vertex pair 的数量，要比具有一阶邻近性的 vertex pair 的数量要多得多。因此，二阶邻近性的引入能够在刻画网络结构方面提供更多的信息。因此，论文的方法对稀疏网络具有鲁棒性。

   

   论文在五个真实世界的网络数据集和四个真实世界的 application 上进行了实验。结果表明：和 baseline 相比，论文方法生成的 representation 可以显著更好地重建原始网络，并在各种任务和各种网络（包括非常稀疏的网络）上取得相当大的收益。这表明 SDNE 在高度非线性空间中学到的 representation 可以很好地保持网络结构，并且对稀疏网络具有鲁棒性。

   综上所述，论文的贡献如下：

   • 论文提出了一种 Structural Deep Network Embedding 方法（即 SDNE）来执行 network embedding 。该方法能够将数据映射到高度非线性的潜在空间从而保留网络结构，并且对稀疏网络具有鲁棒性。据作者所知，他们是最早使用 deep learning 来学习 network representation 的人之一。

   • 论文提出了一种新的、具有半监督架构的深度模型，它同时优化了一阶邻近性和二阶邻近性。结果，学到的 representation 同时保留了局部网络结构和全局网络结构，并且对稀疏网络具有鲁棒性。

   • 作者在五个真实数据集和四个应用场景上广泛评估了 SDNE 方法。结果证明了该方法在多标签分类、网络重建、链接预测、可视化等方面的优异性能。具体而言，当标记数据稀缺时，论文的方法相比 baseline 得到显著提升（20%）。

2. 相关工作：

   • Deep Neural Network: DNN：representation learning 长期以来一直是机器学习的一个重要问题，许多工作旨在学习样本的 representation 。深度神经网络的最新进展见证了它们具有强大的表达能力，并且可以为多种类型的数据生成非常有用的 representation 。例如 《Imagenet classification with deep convolutional neural networks》 提出了一个七层卷积神经网络来生成 representation 从而用于图像分类。

     然而，据我们所知，处理 network 的 deep learning 工作很少，尤其是学习 network representation 。 《A non-iid framework for collaborative filtering with restricted boltzmann machines》 采用受限玻尔兹曼机进行协同过滤，《Learning deep representations for graph clustering》 采用深度自编码器进行 graph clustering ，《Heterogeneous network embedding via deep architectures》 提出了一种异质深度模型来进行异质数据的 embedding 。我们在两个方面与这些工作不同：

     • 首先，目标不同。我们的工作重点是学习低维的、结构保留的 representation，从而可以在各种下游任务之间使用。

     • 其次，我们同时考虑顶点之间的一阶邻近性和二阶邻近性，从而同时保留局部网络结构和全局网络结构。但是他们仅关注单个阶次的信息。

   • Network Embedding：我们的工作是解决 network embedding 问题，旨在学习网络的 representation 。

     一些早期的工作，如 Local Linear Embedding: LLE、IsoMAP 首先基于特征向量（ feature vector ）构建 affinity graph ，然后将主要的特征向量（ leading eigenvector ）作为 network representation 。

     最近，LINE 设计了两个损失函数，试图分别捕获局部网络结构和全局网络结构。此外，GraRep 将工作扩展到利用高阶信息。尽管这些 network embedding 方法取得了成功，但是它们都采用了浅层模型。正如我们之前所解释的，浅层模型很难有效地捕获到底层网络中的高度非线性结构。此外，尽管他们中的一些人尝试使用一阶邻近性和高阶邻近性来保留局部网络结构和全局网络结构，但是他们分别独立地学习保留局部结构的 representation 和保留全局结构的 representation 并简单地拼接起来。显然，与在统一框架中同时建模并捕获局部网络结构和全局网络结构相比，他们的做法是次优的。

     DeepWalk 结合了随机游走和 SkipGram 来学习 network representation 。尽管在经验上是有效的，但是它缺乏明确的目标函数来阐明如何保持网络结构。它倾向于仅保留二阶邻近性。然而，我们的方法设计了一个明确的目标函数，旨在通过同时保留一阶邻近性和二阶邻近性，从而同时保留局部结构和全局结构。

1.1 模型

1. 这里我们首先定义问题，然后介绍 SDNE 半监督深度模型，最后对模型进行一些分析和讨论。

1.1.1 问题定义

1. 定义图 $G=(V,E)$$G=(V,E)$，其中 $V=\{v_1,\cdots ,v_n\}$$V=\{v_1,\cdots,v_n\}$ 为顶点集合，$E=\{e_{i,j}\}$$E=\{e_{i,j}\}$ 为边集合。边 $e_{i,j}=(v_i,v_j)$$e_{i,j} = (v_i,v_j)$ 关联一个权重 $s_{i,j}\ge 0$$s_{i,j}\ge 0$ 。如果顶点 $v_i$$v_i$ 和 $v_j$$v_j$ 之间不存在链接，则 $s_{i,j}=0$$s_{i,j} = 0$ ，如果存在链接则对于无权图 $s_{i,j}=1$$s_{i,j} = 1$ 、对于带权图 $s_{i,j}>0$$s_{i,j} \gt 0$ 。

   network embedding 旨在将 graph data 映射到一个低维的潜在空间中，其中每个顶点都表示为一个低维向量。正如我们前面所解释的，局部结构和全局结构都必须同时被保留。接下来我们定义一阶邻近性，它刻画了局部网络结构。

2. 一阶邻近性（First-Order Proximity ）：一阶邻近性描述了顶点之间的 pairwise 邻近性。给定任何一对顶点 $v_i,v_j$$v_i,v_j$ ，如果 $s_{i,j}>0$$s_{i,j} \gt 0$，则 $v_i$$v_i$ 和 $v_j$$v_j$ 之间存在正的一阶邻近性；否则 $v_i$$v_i$ 和 $v_j$$v_j$ 之间的一阶邻近性为零。

   自然地，network embedding 有必要保持一阶邻近性，因为这意味着：如果现实世界网络中的两个顶点存在链接，那么它们总是相似的。例如，如果一篇论文引用了另一篇论文，那么它们应该包含一些共同的主题。然而，现实世界的数据集通常非常稀疏，以至于观察到的链接仅占一小部分。存在许多彼此相似、但是不被任何 edge 链接的顶点。因此，仅捕获一阶邻近性是不够的，因此我们引入二阶邻近性来捕获全局网络结构。

3. 二阶邻近性（Second-Order Proximity）：一对顶点之间的二阶邻近性描述了它们邻域结构（neighborhood structure） 的邻近性。令 ${\mathcal{N}}_i=\{s_{i,1},\cdots ,s_{i,n}\}$$\mathcal N_i = \{s_{i,1},\cdots,s_{i,n}\}$ 为顶点 $v_i$$v_i$ 和其它所有顶点的一阶邻近性，那么顶点 $v_i$$v_i$ 和 $v_j$$v_j$ 的二阶邻近性由 ${\mathcal{N}}_i$$\mathcal N_i$ 和 ${\mathcal{N}}_j$$\mathcal N_j$ 的相似性来决定。

   直观地讲，二阶邻近性假设：如果两个顶点共享许多共同的邻居（common neighbor） ，那么这两个顶点往往是相似的。这个假设已经在许多领域被证明是合理的。例如，在语言学中，如果两个单词总是被相似的上下文包围，那么这两个单词将是相似的（《Context and contextual word meaning》）。如果两个人之间有很多共同的好友，那么这两个人就会成为朋友（《Structure of growing social networks》）。二阶邻近性已经被证明是定义顶点相似性的一个很好的指标，即使这对顶点之间不存在链接，因此可以高度丰富顶点之间的关系。因此，通过引入二阶邻近性，我们能够刻画全局网络结构并缓解数据稀疏问题。

   通过一阶邻近性和二阶邻近性，我们研究了如何在执行 network embedding 时集成二者，从而同时保持局部结构和全局结构。

4. Network Embedding：给定图 $G=(V,E)$$G=(V,E)$，network embedding 旨在学习映射函数 $f:v_i\to {\overrightarrow{\mathbf{y}}}_i\in {\mathbb{R}}^d$$f:v_i\rightarrow \mathbf{\vec y}_i \in \mathbb R^d$ ，其中 $d\ll n$$d\ll n$ 为 embedding 维度。该映射函数的目标是使得 ${\overrightarrow{\mathbf{y}}}_i$$\mathbf{\vec y}_i$ 和 ${\overrightarrow{\mathbf{y}}}_j$$\mathbf{\vec y}_j$ 之间的相似性显式地、同时地保留 $v_i$$v_i$ 和 $v_j$$v_j$ 的一阶邻近性和二阶邻近性。

1.1.2 SDNE 模型

1. 在本文中，我们提出了一种半监督深度模型来执行 network embedding，其整体框架如下图所示。

   具体而言，为了捕获高度非线性的网络结构，我们提出了一种由多个非线性映射函数组成的深度架构，它将输入数据映射到高度非线性的潜在空间中从而捕获网络结构。此外，为了解决结构保持（structure-preserving ）问题和稀疏性问题，我们提出了一个半监督模型来同时利用二阶邻近性和一阶邻近性。

   • 对于每个顶点，我们能够获取它的邻域。因此，我们设计了无监督组件（unsupervised component） ，通过重建每个顶点的邻域结构来保持二阶邻近性。

   • 同时，对于部分顶点 pair 对（因为并不是所有顶点pair 对之间都存在边），我们可以获得它们的成对相似性，即一阶邻近性。因此，我们设计监督组件（supervised component） ，从而利用一阶邻近性作为监督信息来 refine 潜在空间中的 representation 。

   通过在所提出的半监督深度模型中联合优化无监督组件和监督组件，SDNE 可以很好地保持高度非线性的局部网络结构和全局网络结构，并且对稀疏网络具有鲁棒性。接下来我们将详细介绍如何实现半监督深度模型。

   

2. 我们首先描述无监督组件如何利用二阶邻近性来保持全局网络结构。二阶邻近性是指一对顶点的邻域结构有多么相似。因此，为了对二阶邻近性进行建模，首先需要建模每个顶点的邻域。给定一个网络 $G=(V,E)$$G=(V,E)$，我们可以获得它的邻接矩阵 $\mathbf{S}$$\mathbf S$ ，它包含 $n$$n$ 个实例 instance ${\overrightarrow{\mathbf{s}}}_1,\cdots ,{\overrightarrow{\mathbf{s}}}_n$$\mathbf {\vec s}_1,\cdots,\mathbf {\vec s}_n$ 。每个实例 ${\overrightarrow{\mathbf{s}}}_i=(s_{i,1},\cdots ,s_{i,n}{)}^{\mathrm{\top }}$$\mathbf {\vec s}_i = (s_{i,1},\cdots,s_{i,n})^\top$ 描述了顶点 $v_i$$v_i$ 的邻域结构，因此 $\mathbf{S}$$\mathbf S$ 提供了每个顶点的邻域结构信息。利用 $\mathbf{S}$$\mathbf S$，我们扩展了传统的深度自编码器 deep autoencoder 从而保持二阶邻近性。

   这里我们简要回顾深度自编码器的关键思想。深度自编码器是一个无监督模型，它由编码器（ encoder） 和解码器（ decoder ）两部分组成。编码器由多个非线性函数组成，它将输入数据映射到 representation 空间。解码器也由多个非线性函数组成，它将 representation 空间中的 representation 映射到重建空间 reconstruction space 。然后，给定输入 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ ，每一层的 hidden representation 如下所示：

   $$\begin{array}{c}{\overrightarrow{\mathbf{y}}}_i^{(1)}=\sigma ({\mathbf{W}}^{(1)}{\overrightarrow{\mathbf{x}}}_i+{\overrightarrow{\mathbf{b}}}^{(1)})\\ {\overrightarrow{\mathbf{y}}}_i^{(k)}=\sigma ({\mathbf{W}}^{(k)}{\overrightarrow{\mathbf{y}}}_i^{(k-1)}+{\overrightarrow{\mathbf{b}}}^{(k)}),k=2,\cdots ,K\end{array}$$

   其中：

   • $\sigma (\cdot )$$\sigma(\cdot)$ 为非线性激活函数。

   • ${\mathbf{W}}^{(k)}$$\mathbf W^{(k)}$ 为编码器第 $k$$k$ 层的权重参数矩阵，${\overrightarrow{\mathbf{b}}}^{(k)}$$\mathbf{\vec b}^{(k)}$ 为编码器第 $k$$k$ 层的 bias 参数向量。

   • ${\overrightarrow{\mathbf{y}}}_i^{(k)}$$\mathbf{\vec y}_i^{(k)}$ 为编码器第 $k$$k$ 层的 hidden representation ，$K$$K$ 为编码器的层数。

   得到 ${\overrightarrow{\mathbf{y}}}_i^{(K)}$$\mathbf{\vec y}_i^{(K)}$ 之后，我们可以通过编码器的逆过程（即解码器）得到输出 ${\widehat{\overrightarrow{\mathbf{x}}}}_i$$\hat{\mathbf{\vec x}}_i$ 。自编码器的目标是最小化输出和输入的重建误差（ reconstruction error ）。损失函数如下所示：

   $$\mathcal{L}=\sum _{i=1}^n{\Vert {\widehat{\overrightarrow{\mathbf{x}}}}_i-{\overrightarrow{\mathbf{x}}}_i\Vert }_2^2$$

   正如 《Semantic hashing》 所证明的，尽管最小化重建损失（reconstruction loss ）并不能显式保留样本之间的相似性，但是重建准则（ reconstruction criterion ）可以平滑地捕获数据流形（data manifold），从而保留样本之间的相似性。

   然后考虑我们的情况，如果我们使用邻接矩阵 $\mathbf{S}$$\mathbf S$ 作为自编码器的输入，即 ${\overrightarrow{\mathbf{x}}}_i={\overrightarrow{\mathbf{s}}}_i$$\mathbf{\vec x}_i = \mathbf{\vec s}_i$ ，由于每个实例 ${\overrightarrow{\mathbf{s}}}_i$$\mathbf{\vec s}_i$ 都刻画了顶点 $v_i$$v_i$ 的邻域结构，因此重建过程将使具有相似邻域结构的顶点具有相似的潜在 representation 。

   如果网络规模较大，比如一千万个顶点，则 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 的维度高达千万维，这对于深度自编码器是一个严重的挑战。

   然而，由于网络的某些特定属性，这种重建过程不能直接应用于我们的问题。

   • 在网络中，我们可以观察到一些链接，但同时无法观察到许多合法链接（legitimate link）（即理论上应该存在但是由于各种原因导致观察缺失），这意味着：顶点之间观察到链接确实表明顶点的相似性（similarity ），但是没有观察到链接不一定表明顶点的不相似性（ dissimilarity ）。

   • 此外，由于网络的稀疏性，$\mathbf{S}$$\mathbf S$ 中非零元素的数量远远少于零元素的数量。那么，如果我们直接使用 $\mathbf{S}$$\mathbf S$ 作为传统自编码器的输入，那么更容易重构 $\mathbf{S}$$\mathbf S$ 中的零元素。然而，这不是我们想要的。

   为了解决这两个问题，我们对非零元素的重构误差施加了比零元素更大的惩罚。修改后的目标函数为：

   $${\mathcal{L}}_{\text{2nd}}=\sum _{i=1}^n{\Vert ({\widehat{\overrightarrow{\mathbf{x}}}}_i-{\overrightarrow{\mathbf{x}}}_i)\odot {\overrightarrow{\mathbf{c}}}_i\Vert }_2^2={\Vert (\hat{\mathbf{X}}-\mathbf{X})\odot \mathbf{C}\Vert }_F^2$$

   一方面，对零元素的重建损失施加更小的惩罚，从而放松零元素的重建损失。另一方面，对非零元素的重建损失施加更大的惩罚，从而收紧非零元素的重建损失。

   其中：

   • $\odot$$\odot$ 表示 Hadamard 积（逐元素乘积）。

   • ${\overrightarrow{\mathbf{c}}}_i={(c_{i,1},\cdots ,c_{i,n})}^{\mathrm{\top }}$$\mathbf{\vec c}_i = \left(c_{i,1},\cdots,c_{i,n}\right)^\top$ 表示每个元素的惩罚系数。当 $s_{i,j}=0$$s_{i,j} = 0$ 时 $c_{i,j}=1$$c_{i,j} = 1$；当 $s_{i,j}>0$$s_{i,j}\gt 0$ 时 $c_{i,j}=\beta >1$$c_{i,j} = \beta\gt 1$ 。$\mathbf{C}\in {\mathbb{R}}^{n\times n}$$\mathbf C\in \mathbb R^{n\times n}$ 由 ${\overrightarrow{\mathbf{c}}}_i$$\mathbf{\vec c}_i$ 按行组成。

   • $\hat{\mathbf{X}}\in {\mathbb{R}}^{n\times n}$$\hat{\mathbf X}\in \mathbb R^{n\times n}$ 由 ${\widehat{\overrightarrow{\mathbf{x}}}}_i$$\hat{\mathbf{\vec x}}_i$ 按行组成，$\mathbf{X}\in {\mathbb{R}}^{n\times n}$$\mathbf X \in \mathbb R^{n\times n}$ 由 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x }_i$ 按行组成。

   现在通过使用以邻接矩阵 $\mathbf{S}$$\mathbf S$ 作为输入的、修正后的深度自编码器，具有相似邻域结构的顶点将被映射到 representation 空间相近的位置，这将由重建准则（reconstruction criterion ）所保证。换句话讲，我们模型的无监督组件（ unsupervised component ）可以通过重建顶点之间的二阶邻近性来保留全局网络结构。

3. 如前所述，我们不仅需要保留全局网络结构，还必须捕获局部网络结构。我们使用一阶邻近性来表示局部网络结构。一阶邻近性可以视为监督信息，从而约束一对顶点之间潜在 representation 的相似性。因此，我们设计了监督组件（ supervised component ）来利用一阶邻近性。这个监督组件的损失函数定义为：

   $${\mathcal{L}}_{\text{1st}}=\sum _{i,j=1}^n{s}_{i,j}{\Vert {\overrightarrow{\mathbf{y}}}_i^{(K)}-{\overrightarrow{\mathbf{y}}}_j^{(K)}\Vert }_2^2$$

   该损失函数借鉴了 Laplacian Eigenmaps 的思想，即相似的顶点映射到 embedding 空间中很远的地方时会产生惩罚。我们将这个思想融入到深度模型中，从而使得观察到链接的顶点映射到 embedding 空间中相近的位置。结果，该模型保留了一阶邻近性。

   但是 “不相似” 的顶点映射到 embedding 空间中很近的地方时不会产生惩罚。这在 network embedding 中是合理的，因为网络中未观察到链接的顶点之间可能是相似的，未观察到链接是因为链接缺失 missing 。

4. 为了同时保持一阶邻近性和二阶邻近性，我们提出了一个半监督模型，它结合了 ${\mathcal{L}}_{\text{1nd}}$$\mathcal L_\text{1nd}$ 和 ${\mathcal{L}}_{\text{2nd}}$$\mathcal L_\text{2nd}$ 并联合最小化了以下目标函数：

   $$\begin{array}{c}{\mathcal{L}}_{\text{mix}}={\mathcal{L}}_{\text{2nd}}+\alpha {\mathcal{L}}_{\text{1nd}}+\nu {\mathcal{L}}_{\text{reg}}\\ ={\Vert (\hat{\mathbf{X}}-\mathbf{X})\odot \mathbf{C}\Vert }_F^2+\alpha \sum _{i,j=1}^n{s}_{i,j}{\Vert {\overrightarrow{\mathbf{y}}}_i^{(K)}-{\overrightarrow{\mathbf{y}}}_j^{(K)}\Vert }_2^2+\nu {\mathcal{L}}_{\text{reg}}\end{array}$$

   其中：

   • ${\mathcal{L}}_{\text{reg}}$$\mathcal L_\text{reg}$ 为一个 L2 正则化项，用于防止过拟合：

     $${\mathcal{L}}_{\text{reg}}=\frac{1}{2}\sum _{k=1}^K({\Vert {\mathbf{W}}^{(k)}\Vert }_F^2+{\Vert {\hat{\mathbf{W}}}^{(k)}\Vert }_F^2)$$

   • $\alpha ,\nu$$\alpha,\nu$ 为超参数，用于平衡各部分损失之间的重要性。

   换个角度来看，这是一个多任务学习，主任务为保持一阶邻近性的监督学习任务，辅助任务为保持二阶邻近性的无监督学习任务。

5. 为了优化上述损失函数，我们采用随机梯度下降（stochastic gradient descent: SGD ）来求解。注意，由于模型的高度非线性，它在参数空间中存在许多局部最优解。因此，为了找到一个好的参数区域，我们首先使用深度信念网络（ Deep Belief Network ）对参数进行预训练，这在 《Why does unsupervised pre-training help deep learning?》 中已被证明是深度学习参数的基础初始化方法。

1.1.3 分析和讨论

1. 这里我们对提出的 SDNE 半监督深度模型进行一些分析和讨论。

2. 新顶点：network embedding 的一个实际问题是如何学习新顶点的 representation。对于一个新的顶点 $v_k$$v_k$ ，如果它和现有顶点的链接已知，那么我们可以得到它的邻接向量 ${\overrightarrow{\mathbf{s}}}_k=(s_{k,1},\cdots ,s_{k,n}{)}^{\mathrm{\top }}$$\mathbf{\vec s}_k = (s_{k,1},\cdots,s_{k,n})^\top$ ，其中 $s_{k,i}$$s_{k,i}$ 表示新顶点 $v_k$$v_k$ 和现有顶点 $v_i$$v_i$ 之间的边权重。然后我们可以简单地将 ${\overrightarrow{\mathbf{s}}}_k$$\mathbf{\vec s}_k$ 输入到我们的深度模型中，并使用经过训练的参数来获取 $v_k$$v_k$ 的 representation 。这一过程的复杂度是 $O(1)$$O(1)$ 。

   这里直接使用训练好的模型来推断，而没有继续训练的过程。

   如果 $v_k$$v_k$ 和现有顶点之间都不存在链接，那么我们的方法和其它 SOTA 的 network embedding 方法都无法处理。为了处理这种情况，我们可以求助于其它辅助信息，如顶点的内容特征，我们将其留待未来的工作。

3. 训练复杂度：不难看出我们模型的训练复杂度为 $O(ndaI)$$O(ndaI)$ ，其中：$n$$n$ 为顶点数量，$d$$d$ 为隐层的最大维度，$a$$a$ 为网络的average degree，$I$$I$ 为迭代的次数。

   超参数 $d$$d$ 通常与 embedding 向量的维度有关，但是与顶点数量无关。超参数 $I$$I$ 也独立于顶点数量。对于超参数 $a$$a$，在实际应用中通常可以视为一个常数，例如在社交网络中，一个人的最大朋友数量总是有界的。因此，$daI$$daI$ 与 $n$$n$ 无关，因此整体的训练复杂度与网络中的顶点数量成线性关系。

1.2 实验

1. 这里我们在几个真实世界的数据集和 application 上评估我们提出的方法。实验结果表明我们的方法比 baseline 有显著提升。

2. 数据集：为了全面评估 representation 的有效性，我们使用了五个网络数据集，包括三个社交网络（social network ）、一个引文网络（citation network ）、一个语言网络（language network ），并用于三个实际 application ，即多标签分类任务、链接预测任务、可视化任务。考虑到这些数据集的特性，对于每个 application，我们使用一个或多个数据集来评估性能。

   • 社交网络数据集 BLOGCATALOG, FLICKR, YOUTUBE：它们是在线用户的社交网络，每个用户至少标记为一种类别。

     • BlogCatalog：该数据集包含 BlogCatalog 网站上博主之间的社交关系，标签代表通过元数据推断出来的博主兴趣。网络包含 39 种不同标签。

     • Flickr 数据集：Flickr网站用户之间的关系网络。标签代表用户的兴趣组，如“黑白照片”。网络包含195 种不同标签。

     • YouTube 数据集：YouTube 网站用户之间的社交网络。标签代表用户的视频兴趣组，如“动漫、摔跤”。网络包含 47 种不同标签。

     这些标签类别可以用作每个顶点的真实 label，因此它们可以在多标签分类任务上进行评估。

   • ARXIV GR-QC 数据集：这是一个论文协同网络（ paper collaboration network）， 包括了 arXiv 上广义相对论（General Relativity） 和量子力学（ Quantum Cosmology ）领域的论文。每个顶点代表一个作者，边代表两个作者共同撰写了论文。因为我们没有顶点类别信息，因此该数据集用于链接预测任务。

   • 20-NEWSGROUP ：该数据集包含两万个新闻组文档，每篇文档都标记为 20 个类别之一。我们用单词的 tf-idf 向量表示文档，用余弦相似度表示文档之间的相似性。我们可以根据这样的相似性来构建网络，网络中每个顶点代表一篇文档，边代表文档之间的相似性。

     我们选择以下三类标签的文档来执行可视化任务：comp.graphics, rec.sport.baseball, talk.politics.gums。

   总而言之，这些数据集分别代表了加权图/无权图、稀疏图/稠密图、小型图/大型图。因此，数据集可以全面反映 network embedding 方法的特点。数据集的相似统计如下表：

   

3. baseline 方法：我们使用以下五种方法作为 baseline。前四种是 network embedding 方法，最后一种 Common Neighbor 直接预测网络上的链接。Common Neighbor 已被证明是执行链接预测的有效方法。

   • DeepWalk：使用截断的随机游走和 SkipGram 模型来生成network representation 。

   • LINE：分别定义损失函数来保留一阶邻近性和二阶邻近性。在优化损失函数之后，它将一阶邻近性 representation 和二阶邻近性 representation 拼接起来 。

   • GraRep：扩展到高阶邻近性并基于 SVD 分解来求解模型。它也是拼接了一阶邻近性 representation 和高阶邻近性 representation 作为最终的 representation。

   • Laplacian Eigenmaps：通过分解邻接矩阵的拉普拉斯矩阵来生成 network representation ，它仅仅保留了网络的一阶邻近性。

   • Common Neighbor：它仅使用共同邻居的数量来衡量顶点之间的相似性。该方法仅在链接预测任务中作为baseline 方法。

4. 评估指标：在我们的实验中，我们分别执行重建任务、链接预测任务、多标签分类任务、可视化任务。

   对于重建和链接预测，我们使用 precision@k 和 Mean Average Precision: MAP 来评估性能。它们的定义如下：

   • precision@k：

     $$\text{precision}@k(v_i)=\frac{|\{v_j\mid v_i,v_j\in V,\text{index}(v_j)\le k,{\mathrm{\Delta }}_{v_i}(v_j)=1\}|}{k}$$

     其中： $V$$V$ 为顶点集合；$\text{index}(v_j)$$\text{index}({v_j})$ 为预测结果中顶点 $v_j$$v_j$ 在所有顶点预测结果中排名，得分越高排名越靠前；${\mathrm{\Delta }}_{v_i}(v_j)=1$$\Delta_{v_i}(v_j) = 1$ 表示顶点 $v_i$$v_i$ 和 $v_j$$v_j$ 中确实存在边。

     该指标的物理意义为：预测结果的 top k 顶点中，和顶点 $v_i$$v_i$ 真实存在边的顶点比例。

   • Mean Average Precision: MAP：和 precision@k 相比，MAP 更关注排名靠前的结果的表现。其计算公式为：

     $$\text{AP}@k(v_i)=\frac{\sum _{t=1}^k\text{precision}@k(v_i)}{k},\text{MAP}@k=\frac{\sum _{v_i\in V}\text{AP}@k(v_i)}{|V|}$$

   对于多标签分类任务，我们采用 micro-F1 和 macro-F1 指标。

   • macro-F1：给每个类别相等的权重，其定义为：

     $$\text{Macro-F1}=\frac{\sum _{c\in \mathcal{C}}{F}_1(c)}{|\mathcal{C}|}$$

     其中： $\mathcal{C}$$\mathcal C$ 为所有类别的取值空间集合，$F_1(c)$$F_1(c)$ 为类别 $c$$c$ 的 F1 指标。

   • micro-F1：给每个样本相等的权重，其定义为：

     $$\begin{array}{c}\text{Precision}=\frac{\sum _{c\in \mathcal{C}}\text{TP}(c)}{\sum _{c\in \mathcal{C}}(\text{TP}(c)+\text{FP}(c))},\text{Recall}=\frac{\sum _{c\in \mathcal{C}}\text{TP}(c)}{\sum _{c\in \mathcal{C}}(\text{TP}(c)+\text{FN}(c))}\\ \text{Micro-F1}=\frac{2\times \text{Precision}\times \text{Recall}}{\text{Precision}+\text{Recall}}\end{array}$$

     其中： $\mathcal{C}$$\mathcal C$ 为所有类别的取值空间集合，$\text{TP}(c)$$\text{TP}(c)$ 为类别 $c$$c$ 的true positive，$\text{FP}(c)$$\text{FP}(c)$ 为类别 $c$$c$ 的false positive，$\text{FN}(c)$$\text{FN}(c)$ 为类别 $c$$c$ 的false negative。

5. 参数配置：我们在本文中提出了一种多层深度结构（multi-layer deep structure ），层数随着数据集的不同而变化。每一层的维度如下表所示。BLOGCATALOG, ARXIV GR-QC, 20-NEWSGROUP 数据集为三层结构，FLICKR, YOUTUBE 数据集为四层结构。如果我们使用更深的模型，则性能几乎保持不变甚至变得更差。

   

   • 对于我们的方法，超参数 $\alpha ,\beta ,\nu$$\alpha,\beta,\nu$ 是通过在验证集上使用网格搜索来调优的。baseline 的超参数也被调优为最佳值。

   • 随机梯度下降的 mini-batch size 设为 1 。学习率的初始值设为 0.025。每个正样本采样的负样本数量设为 5，样本总数为 100 亿（包括负采样的）。

   • 此外，根据 LINE 的原始论文，当拼接 1-step representation 和 2-step representation 并对最终 embedding 向量执行 L2 归一化时，LINE 会产生更好的结果。我们按照原始论文的方法来获取 LINE 的结果。

   • 对于 DeepWalk，我们将窗口大小设为 10，将 walk length 设为 40，将每个顶点开始的游走数量设为 40。

   • 对于 GraRep，我们将最高的转移矩阵阶次设为 5 。

1.2.1 实验结果

1. 这里我们首先评估重建性能，然后我们报告不同 embedding 方法生成的 network representation 在三个经典的数据挖掘和机器学习application （即多标签分类、链接预测、可视化）上的泛化结果。

   结果中，最佳性能以粗体突出显示。** 表示 0.01 的统计显著性，* 表示 0.05 的统计显著性（成对的 t-test ）。

2. 网络重建 （Network Reconstruction ）：在继续评估我们的方法在实际 application 中的泛化性能之前，我们首先对不同 network embedding 方法的网络重建能力进行基本的评估。这个实验的原因是：一个良好的 network embedding 方法应该确保学到的 embedding 能够保留原始的网络结构。

   我们使用语言网络 ARXIV GR-QC 和社交网络 BLOGCATALOG 作为代表。给定一个网络，我们使用不同的 network embedding 方法来学习network representation，然后预测原始网络的链接。由于原始网络中的现有链接是已知的并且可以作为 ground-truth，因此我们可以评估不同方法的重建性能，即训练集误差。

   注意：这里的误差是训练误差，而不是测试误差。

   我们使用 precision@k 和 MAP 作为评估指标，实验结果如下图所示。可以看到：

   • SDNE 在两个数据集上 MAP 指标始终超越其它baseline。当 $k$$k$ 增加时，SDNE 在两个数据集上 precision@k 始终最高。这表明我们的方法（即 SDNE ）能够很好地保持网络结构。

     具体而言，在 ARXIV GR-QC 数据集上，一直到 $k=10000$$k=10000$ ，我们方法的 precision@k 都可以达到 100% 并保持在 100% 左右。这表明我们的方法几乎可以完美地重建该数据集中的原始网络，特别是考虑到该数据集中的链接总数为 28980 。

   • 尽管 SDNE 和 LINE 都利用了一阶邻近性和二阶邻近性来保留网络结构，但是 SDNE 效果超越了 LINE，原因可能有两个：

     • LINE 采用浅层结构，因此难以捕获底层网络的高度非线性结构。

     • LINE 直接将一阶邻近性 representation 和二阶邻近性 representation 拼接在一起，这比 SDNE 直接联合优化一阶邻近性和二阶邻近性要差。

   • SDNE 和 LINE 均优于仅利用一阶邻近性来保持网络结构的 LE，这表明引入二阶邻近性可以更好的保留网络结构。

   

   

3. 多标签分类（Multi-label Classification ）：我们在本实验中通过多标签分类任务来评估不同 network representation 的效果。顶点的 representation 是从 network embedding 方法生成的，然后作为顶点分类任务中的顶点特征。

   具体而言，我们采用 LIBLINEAR package 来训练分类器。在训练分类器时，我们随机抽取一部分标记顶点作为训练集、剩余顶点作为测试集。对于 BLOGCATALOG 我们随机抽取 10% 到 90% 的顶点作为训练集，剩余顶点作为测试集；对于 FLICKR,YOUTUBE 我们随机抽取 1% 到 10% 的顶点作为训练集，剩余顶点作为测试集。另外我们删除 YOUTUBE 中没有任何类别标签的顶点。我们重复这样的过程 5 次并报告平均的 Micro-F1 和 Macro-F1 指标。

   BLOGCATALOG 结果如下：

   

   FLICKR 结果如下：

   

   YOUTUBE 结果如下：

   

   可以看到：

   • SDNE 的效果始终超越baseline 方法，证明SDNE 学到的 network representation 相比 baseline 可以更好地泛化到分类任务中。

   • 在 BLOGCATALOG 数据集中，当训练数据比例从 60% 降低到 10% 时，我们的方法相对于 baseline 的提升幅度更加明显。这表明：当标记数据有限时，我们的方法可以实现比 baseline 更显著的提升。这种优势对现实世界的 application 尤为重要，因为标记数据通常是稀缺的。

   • 大多数情况下， DeepWalk 的效果是所有 network embedding 方法中最差的。这有两个原因：

     • 首先，DeepWalk 没有显式的目标函数来捕获网络结构。

     • 其次，DeepWalk 使用随机游走来产生顶点的邻居。由于随机性这会引入很多噪音，尤其对于 degree 很高的顶点。

4. 链接预测（Link Prediction ）：在这里我们聚焦于链接预测任务并进行两个实验：第一个实验评估整体性能，第二个实验评估网络的不同稀疏性如何影响不同方法的性能。

   我们在这里使用数据集 ARXIV GR-QC。为了在网络中进行链接预测任务，我们随机隐藏一部分现有链接并使用剩余网络来训练 network embedding 模型。训练之后，我们可以获得每个顶点的 representation，然后使用获得的 representation 来预测未观察到的链接。与重建任务不同（预测训练期间已知的链接），该任务预测训练期间未知的链接，而不是重建现有的链接。因此，该任务可以展示不同 network embedding 方法的预测能力。此外，我们在该任务中添加了 Common Neighbor 方法，因为它已被证明是进行链接预测的有效方法。

   • 对于第一个实验，我们随机隐藏 15% 的现有链接（大约 4000 个链接），并使用 precision@k 作为预测隐藏链接的评估指标。我们逐渐将 $k$$k$ 从 2 增加到 10000，并在下表中报告结果。可以看到：

     • 当 $k$$k$ 增加时，SDNE 方法始终优于其它 network embedding 方法。这证明了 SDNE 学到的representation 对于未观察到的链接具有很好的预测能力。

     • 当 $k=1000$$k=1000$ 时，SDNE 的precision 仍然高于 0.9，而其它方法的 precision 掉到 0.8 以下。这表明 SDNE 对于排名靠前的链接预测的比较准。对于某些实际 application ，如推荐和信息检索，这种优势非常重要。因为这些应用更关心排名靠前的结果是否准确。

     

   • 在第二个实验中，我们通过随机删除原始网络中的一部分链接来改变网络的稀疏性，然后按照上述流程报告不同 network embedding 方法的结果。结果如下图所示。可以看到：

     • 当网络更稀疏时，LE 和 SDNE/LINE 模型之间的差距增大。这表明：二阶邻近性的引入使得学到的representation 对于稀疏网络鲁棒性更好。

     • 当删除 80% 链接时，SDNE 仍然比所有其它方法好。这表明：SDNE 在处理稀疏网络时能力更强。

     

5. 可视化 Visualization ：network embedding 的另一个重要 application 是在二维空间上生成网络的可视化。因此，我们可视化在 20-NEWSGROUP 网络学到的 representation 。我们使用 t-SNE 工具可视化不同 network embedding 方法学到的低维 network embedding 。结果，每篇文档都被映射到二维空间的一个点，不同类别的文档采用不同颜色：rec.sport.baseball 为蓝色、comp.graphics 为红色、talk.politics.guns 为绿色。因此，一个好的可视化结果是相同颜色的点彼此靠近。可视化结果如下图所示。除了可视化结果，我们还使用 Kullback-Leibler: KL 散度作为定量的评估指标。KL 散度越低，可视化性能越好。

   结论：

   • LE 和 DeepWalk 的效果较差，因为不同类别的顶点彼此混合。

   • LINE 虽然不同类别形成了簇，但是中间部分不同类别的文档依然彼此混合。

   • GraRep 效果更好，但是簇的边界不是很清晰。

   • SND 在簇的分组以及簇的边界上表现最佳。

   • SDNE 方法的 KL 散度最低，定量地证明了我们的方法在可视化任务中的优越性。

   

   

1.2.2 参数敏感性

1. 我们在本节中研究参数敏感性。具体而言，我们评估不同的 embedding 维度 $d$$d$、不同超参数 $\alpha$$\alpha$、不同超参数 $\beta$$\beta$ 值如何影响结果。我们在 ARXIV-GRQC 的数据集上报告 precision@k 指标。

2. embedding 维度 $d$$d$ ：我们在下图展示 embedding 维度 $d$$d$ 如何影响性能。可以看到：

   • 最初，当 embedding 维度增加时效果先提升。这是因为更大的维度可以容纳更多的有效信息。

   • 但是，继续增加 embedding 维度将导致效果缓缓下降。这是因为太大的维度会引入更多的噪音，从而降低性能。

   总体而言 embedding 维度 $d$$d$ 很重要，但 SDNE 对此超参数不是特别敏感。

   

3. 超参数 $\alpha$$\alpha$：超参数 $\alpha$$\alpha$ 平衡了一阶邻近性损失和二阶邻近性损失的权重，实验结果如下所示。可以看到：

   • 当 $\alpha =0$$\alpha = 0$ 时，模型性能完全取决于二阶邻近性。当 $\alpha$$\alpha$ 越大，模型越关注一阶邻近性。

   • 当 $\alpha =0.1$$\alpha = 0.1$ 或者 $\alpha =0.2$$\alpha = 0.2$ 时模型性能最佳。这表明：一阶邻近性和二阶邻近性对于刻画网络结构都是必不可少的。

   

4. 超参数 $\beta$$\beta$：超参数 $\beta$$\beta$ 控制了 $\mathbf{S}$$\mathbf S$ 中非零元素的重建。我们展示了 $\beta$$\beta$ 的值如何影响性能，$\beta$$\beta$ 越大模型越倾向于重构非零元素。实验结果如下所示。可以看到：

   • 当 $\beta =1$$\beta = 1$ 时效果不佳。因为 $\beta =1$$\beta = 1$ 表示模型重构 $\mathbf{S}$$\mathbf S$ 时认为零元素和非零元素都是同样重要的。

     如前所述，虽然两个顶点之间没有链接不一定表示两个顶点不相似，但是两个顶点之间存在链接一定表明两个顶点的相似性。因此非零元素应该比零元素更加重要。所以 $\beta =1$$\beta = 1$ 在零元素的重构中引入大量噪声，从而降低模型性能。

   • 当 $\beta$$\beta$ 太大时性能也较差。因为 $\beta$$\beta$ 很大表示模型在重构中几乎忽略了 $\mathbf{S}$$\mathbf S$ 的零元素，模型倾向于认为每一对顶点之间都存在相似性。事实上 $\mathbf{S}$$\mathbf S$ 之间的很多零元素都表明顶点之间的不相似。所以 $\beta$$\beta$ 太大将忽略这些不相似，从而降低模型性能。

   这些实验表明：我们应该更多的关注 $\mathbf{S}$$\mathbf S$ 中非零元素的重构误差，但是也不能完全忽略 $\mathbf{S}$$\mathbf S$ 中零元素的重构误差。